package text;

import java.util.Arrays;
import java.util.Random;

/*归并排序*/
public class MergeSort {
    public static void main(String[] args) {
        /*创建需要排序的数组对象*/
        Random random = new Random();
        int[] values = new int[10];
        for (int i = 0;i < values.length;i++){
            values[i] = random.nextInt(1000);
        }
        /*输出数组，观察原数组*/
        System.out.println("原数组"+Arrays.toString(values));
        /*调用mergeSort方法进行排序*/
        int[] finalArray = mergeSort(values,0,values.length - 1);
        /*输出数组，观察最终的结果*/
        System.out.println("排序后"+Arrays.toString(finalArray));
    }
    /*这是一个自定义方法，方法的声明可以参考main（）方法
    * @param value 原数组
    * @param start 需要被拆分的的区间的起始元素下
    * @param end 需要被拆分的区间的结束元素下标
    * @return 合并的数组*/
    public static int[] mergeSort(int[] array,int start,int end){
        /*为防止递归出现死循环，当end与start相同时（发生在尝试对长度为1的数组再拆分），不必再执行*/
        if (end == start){
            /*使用return返回当前片段的新数组*/
            return new int[]{array[start]};
        }
        /*求数组需要被拆分的区间的中间点*/
        int mid = start+(end-start)/2;
        /*创建两个新的数组，分别表示拆分后的左侧和右侧呃呃区域*/
        int[] leftArray = mergeSort(array,start,mid);
        int[] rightArray = mergeSort(array,mid+1,end);
        /*创建新的数组，用于存放合并后的有序结果*/
        int[] newArray = new int[leftArray.length+rightArray.length];
        /*声明变量，l,r,n分别表示leftArray，rightArray，newArray的下标变量*/
        int l = 0;
        int r = 0;
        int n = 0;
        /*当leftArray和rightArray都遍历结束之前，一直循环*/
        while (l<leftArray.length && r<rightArray.length){
            /*对比数组中的元素*/
           /* if (leftArray[l] <= rightArray[r]){
           //左侧数组的元素更小，将左侧数组的元素放到新数组中
                newArray[n++] = leftArray[l++];
                //左侧数组的下标变量自增
                l++;
                //新数组的下标变量自增
                n++;
            }else {
            //右侧数组的元素更小，将右侧数组的元素放到新数组中
                newArray[n++] = rightArray[r++];
                //右侧数组的下标变量自增
            }*/
           newArray[n++] = leftArray[l]<rightArray[r] ? leftArray[l++] : rightArray[r++];
        }
        /*新数组的下标变量自增
        * n++;*/
        /*如果左侧数组还有剩余，可直接依次全部填充到新数组*/
        while (l<leftArray.length){
            newArray[n++] = leftArray[l++];
        }
        /*如果右侧侧数组还有剩余，可直接依次全部填充到新数组*/
        while (r<rightArray.length){
            newArray[n++] = rightArray[r++];
        }
        /*返回新数组*/
        return newArray;
    }

}
